﻿// 0805train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;


/*
 给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。
 另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。

示例1
输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例2
输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2
 */
//nums = [9, 4, 1, 7], k = 2


int solve01(vector<int>&nums, int k)
{
    vector<int>oh_vec = nums;
    int vec_size = oh_vec.size();
    int limit = k;

    sort(oh_vec.begin(), oh_vec.end());
    int result = oh_vec[limit - 1] - oh_vec[0];

    for (int right=k,left=1; right<vec_size; left++, right++)
    {
        result = min(result, oh_vec[right]-oh_vec[left]);
    }

    return result;
    //solve01
}


/*
 给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
示例 1：
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。
示例 2：
输入：s = "aeiou", k = 2
输出：2
解释：任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3：
输入：s = "leetcode", k = 3
输出：2
解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
示例 4：
输入：s = "rhythms", k = 4
输出：0
解释：字符串 s 中不含任何元音字母。
示例 5：
输入：s = "tryhard", k = 4
输出：1
 */

int GetTargetCount(string &mini_str, const unordered_set<char>&target_set)
{
    //cout << "mini_str " << mini_str.size() << endl;
    int count = 0;
    for (auto&oh_char: mini_str)
    {
        if (target_set.count(oh_char))
        {
            count += 1;
        }
    }

    return count;
	//GetTargetCount
}

int GetSubCount(string & sub_prev, const unordered_set<char>& target_set)
{
    if (target_set.count(sub_prev[0]))
    {
        return 1;
    }

    return 0;
}

int GetCurrCount(int curr_count, string&prev_str, string&curr_str, const unordered_set<char>&target_set)
{

	int prev_sub_count = GetSubCount(prev_str, target_set);
	int curr_sub_count = GetSubCount(curr_str, target_set);

	return curr_count - prev_sub_count + curr_sub_count;
    
}

int solve02(string&s, int k)
{
    string target_str = "aeiou";
    unordered_set<char>target_set;

    for (auto&oh_char:target_str)
    {
        target_set.insert(oh_char);
    }

    string oh_str = s;
    int str_size = oh_str.size();
    int limit = k;

    if (str_size==1)
    {
        return GetTargetCount(oh_str, target_set);
    }

    string init_str = oh_str.substr(0, limit);
    int result = GetTargetCount(init_str, target_set);

    int curr_count = result;

    //prev_str存左窗（即将丢弃）
    string prev_str = init_str.substr(0, 1);
    for (int left_index=1,right_index=limit; right_index<str_size; left_index++,right_index++)
    {
        //curr_str存右窗（新加入）
        string curr_str = oh_str.substr(right_index, 1);
        curr_count = GetCurrCount(curr_count, prev_str, curr_str, target_set);

        prev_str = oh_str.substr(left_index,1);
        result = max(result, curr_count);
        //cout << "curr_count " << curr_count << endl;
    }
    return result;
    //solve02
}



/*
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。 
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
 */

bool IsContain(string&oh_str, string&target_str, unordered_map<char, int>&oh_map)
{
    for (auto&oh_char:oh_str)
    {
	    if (oh_map.count(oh_char))
	    {
            oh_map[oh_char] -= 1;
	    }
    }

    for (auto&map_item:oh_map)
    {
        if (map_item.second!=0)
        {
            return false;
        }

    }
    return true;
}

bool IsWindowContain(string&prev_str,string&curr_str, unordered_map<char, int>& oh_map)
{
	if (oh_map.count(prev_str[0]))
	{
        oh_map[prev_str[0]] += 1;
	}

    if (oh_map.count(curr_str[0]))
    {
        oh_map[curr_str[0]] -= 1;
    }
    for (auto& map_item : oh_map)
    {
        if (map_item.second != 0)
        {
            return false;
        }

    }
    return true;
    //IsWindowContain
}

bool solve03(string&s1, string&s2)
{
    //1移动窗口
    //2窗口中是否包含排列,包含return true
    string target_str = s1;
    int window_length = s1.size();

    string oh_str = s2;
    int str_size = oh_str.size();

    unordered_map<char, int>oh_map;
    for (auto& oh_char : target_str)
    {
        oh_map[oh_char] += 1;
    }

    string init_str = oh_str.substr(0, window_length);
    bool result = IsContain(init_str, target_str, oh_map);


    if (result) return true;
    //左窗字符（即将丢弃）
    string prev_str = init_str.substr(0,1);
    for (int left_index=1, right_index= window_length; right_index< str_size; left_index++,right_index++)
    {
        //右窗字符（新加入）
        string curr_str = oh_str.substr(right_index,1);

        if (IsWindowContain(prev_str,curr_str,oh_map))
        {
            return true;
        }
        prev_str = oh_str.substr(left_index, 1);
        //for------
    }

    return false;
    //solve03
}

/*
 有一个书店老板，他的书店开了 n 分钟。
 每分钟都有一些顾客进入这家商店。
 给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，
 所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
 
示例 1：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例 2：
输入：customers = [1], grumpy = [0], minutes = 1
输出：1
 */

int GetTotalCount(int left_index, int right_index, const vector<int>&oh_vec,
    const vector<int>&sequence_vec)
{
    int count = 0;
    for (int i=0;i<oh_vec.size();i++)
    {
        if (i>=left_index&&i<=right_index)
        {
            count += oh_vec[i];
        }
        else
        {
            count += (oh_vec[i] * sequence_vec[i]);
        }
        
    }

    return count;
	//GetTotalCount
}

int GetWindowCount(int prev_index,int new_index, int curr_count,
    const vector<int>& oh_vec, const vector<int>& sequence_vec)
{
    //[1,0,1,2,1,1,7,5]
    //[1,0,1,0,1,0,1,0]
    //如果prev是1，那么不用处理
    //如果prev是0，才要减掉
    if (sequence_vec[prev_index]==0)
    {
        int prev_num = oh_vec[prev_index];
        curr_count = curr_count - prev_num;
    }
	if (sequence_vec[new_index]==0)
	{
        int new_num = oh_vec[new_index];
        curr_count = curr_count + new_num;
	}
	return curr_count;

}

int solve04(vector<int>& customers, vector<int>& grumpy, int minutes)
{
    vector<int>oh_vec = customers;
    int vec_size = customers.size();
    int win_length = minutes;

    vector<int>sequence_vec(vec_size);
    for (int i=0;i<vec_size;i++)
    {
        if (grumpy[i]==0)
        {
            sequence_vec[i] = 1;
        }
        else
        {
            sequence_vec[i] = 0;
        }
    }
    int result = GetTotalCount(0, win_length - 1, oh_vec, sequence_vec);
    int curr_total = result;
    //左窗（即将丢弃）
    int prev_index = 0;
    for (int left_index=1,right_index=win_length; right_index<vec_size; left_index++,right_index++)
    {

        curr_total = GetWindowCount(prev_index, right_index, curr_total, oh_vec, sequence_vec);

        result = max(result, curr_total);

        prev_index = left_index;
    }

    return result;
    //solve04
}


/*
 在一个狭小的路口，每秒只能通过一辆车，
 假如车辆的颜色只有 3 种，找出 N 秒内经过的最多颜色的车辆数量，
 三种颜色编号为 0, 1, 2。
输入
第一行输入的是通过的车辆颜色信息。比如[0, 1, 1, 2] 代表 4 秒钟通过的车辆颜色分别是 0, 1, 1, 2
第二行输入的是统计时间窗，整型，单位为秒。
输出
输出指定时间窗内经过的最多颜色的车辆数量

输入
0 1 2 1
3
输出
2

在[1,2,1]这个 3 秒时间窗内，1 这个颜色出现 2 次，数量最多
 */
int GetTotalCount05(int left_index,int right_index, vector<int>& oh_vec)
{
    unordered_map<int, int>oh_map;
    vector<pair<int, int>>sort_vec;

    for (int i=left_index;i<=right_index;i++)
    {
        oh_map[oh_vec[i]] += 1;
    }
    for (auto&map_item:oh_map)
    {
        pair<int, int>oh_pair = make_pair(map_item.first, map_item.second);
        sort_vec.push_back(oh_pair);
    }
    sort(sort_vec.begin(), sort_vec.end(), [](pair<int, int>& a, pair<int, int>& b)
        {
            return a.second > b.second;
        });
    return sort_vec[0].second;
    //---
}

void solve05(vector<int>&oh_vec, int win_length)
{
    int vec_size = oh_vec.size();

    if (win_length > vec_size)
    {
        int result = GetTotalCount05(0, vec_size - 1, oh_vec);
        cout << result;
        return;
    }

    int result = GetTotalCount05(0, win_length-1, oh_vec);

    for (int left_index=1,right_index=win_length;right_index<vec_size;left_index++,right_index++)
    {
        int curr_count = GetTotalCount05(left_index, right_index, oh_vec);
        result = max(result, curr_count);
    }

    cout << result;
    //solve05
}


int main()
{
	{
        //0 1 2 1
		//3
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<int>oh_vec;
        while (oh_sstream>>token)
        {
            oh_vec.push_back(stoi(token));
        }
        int win_length;
        cin >> win_length;
        //vector<int>oh_vec = { 0,1,2,1 };
        //int win_length = 3;
        solve05(oh_vec, win_length);
        return 0;
	}

	{
        //customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
        vector<int>customers = { 1,0,1,2,1,1,7,5 };
        vector<int>grumpy = { 0,1,0,1,0,1,0,1 };
        int minutes = 3;

        cout<<solve04(customers, grumpy, minutes);

        return 0;
	}

	{
        //s1 = "ab" s2 = "eidbaooo" true

        string s1 = "ab";
        string s2 = "eidbaooo";
        cout << solve03(s1, s2);

        return 0;
	}

	{
        //s = amqlgjitwetesmbbymgjbufptuspnduwsqxmqdvkydwipwllbktrseugnob, k = 31
        //s = "leetcode", k = 3
        //s = "abciiidef", k = 3 3
        string s = "abciiidef";
        int k = 3;

        cout << solve02(s, k);
        return 0;
	}

    //nums = [9, 4, 1, 7], k = 2
    vector<int>nums = { 9, 4, 1, 7 };
    int k = 2;
    cout << solve01(nums, k);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
